# LeetCode 207、课程表
# 一、题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 1050 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对 互不相同
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 课程表（LeetCode 207）：https://leetcode.cn/problems/course-schedule/submissions/
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 尝试在不具备图的基础知识的情况下来做这题
// 本题的核心点在于处理任意一个课程的时候，都需要考虑它是否有前置课程没有完成
// 只有说当前这个课程没有前置课程才能去处理它
// 1、记录每一个课程的情况
// 即，记录课程号与课程前置课程数量
// 使用哈希表来记录，可以快速获取和新增结果
// 在图这种数据结构里面专业术语叫做记录每个课程的【入度】
// key: 课号
// value: 学习这门课程的前置课程数量
Map<Integer, Integer> inDegree = new HashMap<>();
// 2、初始化哈希表
for (int i = 0; i < numCourses; i++) {
// 3、每个课程的前置课程默认都是 0
inDegree.put(i, 0);
}
// 4、记录每个课程直接的依赖关系
// 从而知道完成某个课程的时候，其它哪些课程被影响到了
// 由于被影响的课程可能有很多个，所以采用数组的形式保存被影响的那些课程
// 依赖关系，在图这种数据结构里面专业术语叫做邻接表
// key: 课号
// value: 依赖这门课的后续课，涉及多门，数组保存
Map<Integer, List<Integer>> map = new HashMap<>();
// 5、遍历 prerequisites 数组
// 更新 inDegree 与 map
for (int[] arr : prerequisites) {
// prerequisites 数组中的每一个元素都是数组的形式
// 每一个元素记录了两个数据
// [first , second ]
// 学 first 的前置课程之一是完成 second
// 完成 second 会影响 first 的前置课程数量
int first = arr[0];
int second = arr[1];
// 6、更新入度
// 即更新 first 的前置课程数量，加 1 操作
inDegree.put(first, inDegree.get(first) + 1);
// 7、更新依赖
// 即记录 second 会影响哪些课程
// 此时 ， second 必然会影响 first
if (!map.containsKey(second)) {
map.put(second, new ArrayList<>());
}
// 8、更新 second 影响的课程
map.get(second).add(first);
}
// 9、开始去选修课程，只有没有前置课程的课程才能去选修
// 即入度为 0 的课程才能去选修
// 完成了一个入度为 0 的课程之后，会影响它的后续课，如果后续课为 0 了，又能选修了
// 以此类推
// 一开始把所有入度为 0 的课程都加入到队列里面
Queue<Integer> q = new LinkedList<>();
for (int key : inDegree.keySet()) {
if (inDegree.get(key) == 0) {
q.offer(key);
}
}
// 10、每个课程依次出列进行处理
// a、减小相关课的入度
// b、如果相关课的入度变为 0，也可以加入到队列里面
// 直到队列为空，即没有课程可以选修为止
while (!q.isEmpty()) {
// 课程出队
int course = q.poll();
// 如果发现该课程不会对任何一个课程有影响
// 即，如果发现依赖关系（邻接表）没有 course
// 那么直接去查看下一个课程的情况
if (!map.containsKey(course)) {
continue;
}
// 否则开始更新当前课程的所有后续课程的【入度】情况
// 获取当前课程的所有的后续课程
List<Integer> successorList = map.get(course);
// 更新后续课程的【入度】情况
for (int k : successorList) {
// 当前课程 course 选修完毕之后
// 每个后续课程的前置课程数量减一
// 即【入度】减一
inDegree.put(k, inDegree.get(k) - 1);
// 如果发现后续某个课程【入度】为零
if (inDegree.get(k) == 0) {
// 把它也加入到队列处理
q.offer(k);
}
}
}
// 11、由于只有入度为零的课程才能被选修
// 因此，遍历 inDegree，查看是否还有入度为非零的课程
for (int key : inDegree.keySet()) {
// 如果有，说明当前课程无法被选修
if (inDegree.get(key) != 0) {
// 即无法完成所有课程的学习
return false;
}
}
// 12、否则说明可以完成所有课程的学习
return true;
}
}
# **2、**C++ 代码
# 3、Python 代码
登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 微信：278166530
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 尝试在不具备图的基础知识的情况下来做这题
# 本题的核心点在于处理任意一个课程的时候，都需要考虑它是否有前置课程没有完成
# 只有说当前这个课程没有前置课程才能去处理它
# 1、记录每一个课程的情况
# 即，记录课程号与课程前置课程数量
# 使用哈希表来记录，可以快速获取和新增结果
# 在图这种数据结构里面专业术语叫做记录每个课程的【入度】
# key: 课号
# value: 学习这门课程的前置课程数量
# 2、初始化哈希表
inDegree = [0] * numCourses
# 4、记录每个课程之间的依赖关系
# 从而知道完成某个课程的时候，其它哪些课程被影响到了
# 由于被影响的课程可能有很多个，所以采用数组的形式保存被影响的那些课程
# 依赖关系，在图这种数据结构里面专业术语叫做邻接表
# key: 课号
# value: 依赖这门课的后续课，涉及多门，数组保存
map = defaultdict(list)
# 5、遍历 prerequisites 数组
# 更新 inDegree 与 map
for arr in prerequisites:
# prerequisites 数组中的每一个元素都是数组的形式
# 每一个元素记录了两个数据
# [first , second ]
# 学 first 的前置课程之一是完成 second
# 完成 second 会影响 first 的前置课程数量
first = arr[0]
second = arr[1]
# 6、更新入度
# 即更新 first 的前置课程数量，加 1 操作
inDegree[first] += 1
# 7、更新依赖
# 即记录 second 会影响哪些课程
# 此时 ， second 必然会影响 first
if map.get(second) == None:
map[second] = []
# print(map[second])
map[second].append(first)
# 9、开始去选修课程，只有没有前置课程的课程才能去选修
# 即入度为 0 的课程才能去选修
# 完成了一个入度为 0 的课程之后，会影响它的后续课，如果后续课为 0 了，又能选修了
# 以此类推
# 一开始把所有入度为 0 的课程都加入到队列里面
q = deque()
for i in range(len(inDegree)):
if inDegree[i] == 0:
q.append(i)
# 10、每个课程依次出列进行处理
# a、减小相关课的入度
# b、如果相关课的入度变为 0，也可以加入到队列里面
# 直到队列为空，即没有课程可以选修为止
while q:
# 课程出队
course = q.popleft()
# print(course)
# 如果发现该课程不会对任何一个课程有影响
# 即，如果发现依赖关系（邻接表）没有 course
# 那么直接去查看下一个课程的情况
if map.get(course) == None :
continue
# 否则开始更新当前课程的所有后续课程的【入度】情况
# 获取当前课程的所有的后续课程
successorList = map.get(course)
# 更新后续课程的【入度】情况
for k in successorList :
# 当前课程 course 选修完毕之后
# 每个后续课程的前置课程数量减一
# 即【入度】减一
inDegree[k] -= 1
# 如果发现后续某个课程【入度】为零
if inDegree[k] == 0 :
# 把它也加入到队列处理
q.append(k)
# 11、由于只有入度为零的课程才能被选修
# 因此，遍历 inDegree，查看是否还有入度为非零的课程
for key in inDegree :
# 如果有，说明当前课程无法被选修
if key != 0 :
# 即无法完成所有课程的学习
return False
# 12、否则说明可以完成所有课程的学习
return True